package com.li.tree;

import java.util.LinkedList;

/**  
* 类说明   
*  
* @author ****  
* @date 2018年4月10日  新建  
*/
public class BinaryTree {
	Node root = null;
	public BinaryTree(Node root){
		this.root = root;
	}
	
	static class Node{
		int key;
		String value;
		Node left;
		Node right;
		
		public Node(int key, String value){
			this.key = key;
			this.value = value;
		}
	}
	
	public static void main(String[] args) {
		BinaryTree bt = new BinaryTree(new Node(5,"5"));
		Node root  = bt.root;
		Node node1 = new Node(1,"1");
		Node node2 = new Node(2,"2");
		Node node3 = new Node(3,"3");
		Node node6 = new Node(6,"6");
		Node node7 = new Node(7,"7");
		Node node8 = new Node(8,"8");
		
		root.left = node3;
		node3.left = node1;
		node1.right = node2;
		
		root.right = node6;
		node6.right = node7;
		node7.right = node8;
		
		addNode(root, 10, "10");
		addNode(root, 4, "4");
		
		levelTree(root);
		System.out.println();
		mLRTree(root);
		System.out.println();
		lMRTree(root);
		System.out.println();
		lRMTree(root);
	}
	
	public static void addNode(Node root,int key, String value){
		if(root == null){
			root = new Node(key,value);
			return;
		}else{
			if(key < root.key){
				if(root.left == null){
					root.left = new Node(key,value);
					return;
				}
				addNode(root.left,key,value);
			}else if(key > root.key){
				if(root.right == null){
					root.right = new Node(key,value);
					return;
				}
				addNode(root.right,key,value);
			}else{
				root.value = value;
			}
		}
	}
	
	public static void levelTree(Node root){
		Node node = null;
		if(root == null){
			return;
		}
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		while(!queue.isEmpty()){
			node = queue.poll();
			System.out.print(node.key+" ");
			if(node.left!=null){
				queue.offer(node.left);
			}
			if(node.right!=null){
				queue.add(node.right);
			}
		}
	}
	
	public static void mLRTree(Node root){
		if(root == null){
			return;
		}
		System.out.print(root.key+" ");
		mLRTree(root.left);
		mLRTree(root.right);
	}
	
	public static void lMRTree(Node root){
		if(root == null){
			return;
		}
		lMRTree(root.left);
		System.out.print(root.key+" ");
		lMRTree(root.right);
	}
	
	public static void lRMTree(Node root){
		if(root == null){
			return;
		}
		lRMTree(root.left);
		lRMTree(root.right);
		System.out.print(root.key+" ");
	}
}
  